package letcode.problem.dynamicProgra;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/maximal-square/solutions/234964/zui-da-zheng-fang-xing-by-leetcode-solution/?envType=study-plan-v2&envId=dynamic-programming
 * */
public class MaximalSquare {
    public static int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        if (m == 1 && n == 1) {
            return Integer.parseInt(matrix[0][0]+"");
        }

        int[][] dp = new int[m][n];

        for (int i = 0; i < matrix[0].length; i++) {
            dp[0][i] = Integer.parseInt(matrix[0][i]+"");
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = Integer.parseInt(matrix[i][0]+"");
        }

        for (int i = 1; i < m; i++) {
            for (int i1 = 1; i1 < n; i1++) {
                if (matrix[i][i1] == '1') {
                    dp[i][i1] = Math.min(Math.min(dp[i][i1 - 1], dp[i - 1][i1]), dp[i - 1][i1 - 1]) + 1;
                }else {
                    dp[i][i1] = 0;
                }

            }
        }

        int b = Arrays.stream(dp).flatMapToInt(Arrays::stream).max().orElse(0);
        return b * b;
    }

    public static void main(String[] args) {
        System.out.println(maximalSquare(
                new char[][]{
                        {'1', '0', '1', '0', '0'},
                        {'1', '0', '1', '1', '1'},
                        {'1', '1', '1', '1', '1'},
                        {'1', '0', '0', '1', '0'}
                }
        ));
    }
}
